//反转一个单链表。 
//
// 示例: 
//
// 输入: 1->2->3->4->5->NULL
//输出: 5->4->3->2->1->NULL 
//
// 进阶: 
//你可以迭代或递归地反转链表。你能否用两种方法解决这道题？ 
// Related Topics 链表 
// 👍 1372 👎 0

package com.leetcode.editor.cn;

//Java：反转链表
class P206ReverseLinkedList {
    public static void main(String[] args) {
        Solution solution = new P206ReverseLinkedList().new Solution();
        // TO TEST
        ListNode listNode = new ListNode(1, null);
        listNode.next = new ListNode(2, null);
        listNode.next.next = new ListNode(3, null);
        listNode.next.next.next = new ListNode(4, null);
        ListNode reverseList = solution.reverseList(listNode);
        while (reverseList != null) {
            System.out.println(reverseList.value);
            reverseList = reverseList.next;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode reverseList(ListNode head) {
            if (head == null) {
                return null;
            }
            //1.暴力解法，两次遍历
//            List<ListNode> list = new ArrayList<>();
//            while (head != null) {
//                list.add(head);
//                head = head.next;
//            }
//            ListNode node = list.get(list.size() - 1);
//            ListNode listNode = node;
//            for (int i = list.size() - 2; i >= 0; i--) {
//                node.next = list.get(i);
//                node = list.get(i);
//            }
//            node.next = null;
//            return listNode;
            //2双指针
            ListNode pre = null;
            ListNode curr = head;
            while (curr != null) {
                ListNode temp = curr.next;
                curr.next = pre;
                pre = curr;
                curr = temp;
            }
            return pre;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    static class ListNode {
        int value;
        ListNode next;

        public ListNode(int value, ListNode next) {
            this.value = value;
            this.next = next;
        }
    }
}